#include"SO.h"

void Swap(int* x, int* y)
{
	int temp = *y;
	*y = *x;
	*x = temp;
}

void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0, end = n - 1;
	while (begin <= end)
	{
		int mini = begin, maxi = end;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
				mini = i;

			if (a[i] > a[maxi])
				maxi = i;
		}
		Swap(&a[begin], &a[mini]);

		if (begin == maxi)
		{
			maxi = mini;
		}

		Swap(&a[begin], &a[maxi]);
	}
	
}

void BubbleSort(int* a,int n)
{
	assert(a);

	for (int i = 0; i < n; ++i)
	{
		int exchange = 0;
		for (int j = 1; j < n - i; ++j)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				exchange = 1;
			}
		}

		if (exchange == 0)
		{
			break;
		}
	}
}

void QuickSort(int* a, int n)
{
	int left = 0, right = n - 1;
	int key = a[left];
	while (left<right)
	{
		while (a[right] > key)
		{
			--right;
		}
		while (a[left] < key)
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

}